//map
class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int>& numbers) {
        map<int,int> m;
        for(auto& e:numbers)
        {
            m[e]++;
        }
        int len=numbers.size()/2;
        for(auto& e:m)
        {
            if(e.second>len)
            return e.first;
        }
        return 0;
    }
};
//投票法
class Solution {
  public:
    int MoreThanHalfNum_Solution(vector<int>& numbers) {
        //投票法
        int ret = 1; //票数
        int cnt = 0; //候选者
        for (int i = 1; i < numbers.size(); i++) {
            if (numbers[i] != numbers[cnt])
            {
                ret--;
            }
            else {
                ret++;
            }
            if (ret == 0) {
                ret = 1;
                cnt = i;
            }
            printf("%d ",ret);
        }
        return numbers[cnt]; 
    }
};